package main.adt.stack;

import java.util.Arrays;

/**
 * Created by july on 2015/12/20.
 *
 * 栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底。
 * 不含任何数据元素的栈称为空栈，栈又称为后进先出(last in first out)的线性表，简称LIFO结构。
 * 常用操作：
 * 1、初始化建立一个空栈
 * 2、返回栈的长度，返回栈中数据元素个数。
 * 3、入栈(进栈/压栈)，向栈顶插入一个数据元素，栈长度+1
 * 4、出栈(弹栈)，从栈顶删除一个数据元素，栈长度-1，该方法通常返回被删除的数据元素
 * 5、访问栈顶元素，返回栈顶的数据元素，但不删除。
 * 6、判断是否为空栈，若为空返回true，不为空返回false。
 * 7、清空栈
 *
 * 栈的顺序存储---顺序栈
 */
public class SequenceStack<E> {

    private static final int DEFAULT_CAPACITY = 8;  //默认初始容量

    private int capacity;                           //当前容量
    private int size;                               //当前元素个数
    private Object[] data;                          //数据

    public SequenceStack(){
        this(DEFAULT_CAPACITY);
    }

    public SequenceStack(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("初始集合时capacity参数值不能小于0");
        }
        this.data = new Object[capacity];
        this.capacity = capacity;
    }

    /**
     * 入栈
     * @param element
     */
    public void push(E element){
        ensureCapacity(size + 1);
        data[size++] = element;
    }

    /**
     * 出栈
     * @return
     */
    public E pop(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("当前栈为空，无法出栈");
        }
        E oldEle = (E) data[size - 1];
        data[--size] = null; //一定要加上这句，防止内存泄漏
        return oldEle;
    }

    /**
     * 访问栈顶元素
     * @return
     */
    public E peek(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("当前栈为空，无法访问栈顶元素");
        }
        return (E) data[size - 1];
    }

    /**
     * 判断是否为空栈
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 返回栈的长度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 清空栈
     */
    public void clear(){
        Arrays.fill(data, null);
        size = 0;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString() {
        if(size == 0){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Object temp;
        for(int i = 0;i < size;i++){
            temp = data[i];
            if(temp != null){
                sb.append(temp.toString()).append(',');
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    /**
     * 由于盛装数据的数组容器的容量是固定的，所以在每次插入新数据之前要先检查集合的容量是否
     * 能容纳新添加的数据元素。
     * 判断方法：
     *  如果集合中的元素已经达最大值,直接抛出异常（如果size=Integer.MAX_VALUE,那么size+1会小于0）
     *  如果所需容量大于当前容量，就将集合容量增加1.5倍，增加后判断容量是否溢出，如果增加后的容量减去
     *  所需容量小于0就说明增加后的容量溢出了，此时就将所需容量作为增加后的容量。
     *  容量增加后就将集合中的数据复制到新数组里。
     * @param minCapacity
     */
    private void ensureCapacity(int minCapacity) {
        if(minCapacity <= 0){
            throw new IllegalArgumentException("当前集合容量已达最大值，无法继续增加容量");
        }
        if(minCapacity > capacity){
            while(capacity < minCapacity){
                capacity = capacity + capacity >> 1;
            }
            if(capacity - minCapacity < 0){
                capacity = minCapacity;
            }
            data = Arrays.copyOf(data, capacity);
        }
    }
}
